1. Field
This invention relates to allocation of a limited resource among multiple users. More specifically, this invention relates to the assignment of usage rates based on a set of persistence vectors.
2. Background
A shared resource is one which may be used by multiple users. Shared resources which have limited availabilities or capacities include such diverse examples as electric power stations and other energy plants, water sources such as reservoirs and flowing bodies, supply systems for the distribution of goods and/or material, and data communications networks and pathways. Problems associated with allocating the use of a shared resource among multiple users may therefore arise in many different contexts. Regardless of the particular context, however, such resources may be found in many systems in which at least the following conditions hold:
the capacity or availability of the shared resource may be expressed in terms of a finite rate R of units per measure of time (e.g. kilowatts/hour, gallons/minute, cartons/week, or bits/second);
at any particular time, the resource is being used by n different users, where n is a non-negative integer; and
at any particular time, the usage of the i-th user (where 1≦i≦n) may be characterized by a finite usage rate ui of units per measure of time.
A basic model for such a system is shown in FIG. 1, where resource 100 is used by users 120A-D at rates 110A-D, respectively. Depending on the particular implementation, the rate R which characterizes the shared resource may indicate an actual or estimated limit of the capacity of the resource (e.g., in the case of a communications pathway) or, in the alternative, the rate R may be a threshold indicating a maximum safe or permissible load of the resource (e.g., in the case of a power generation facility or device). Likewise, the usage rates ui may indicate actual use, expected use, or requests or demands for use.
An overload condition arises when the sum of the n usage rates ui at any one time exceeds the value R. With respect to a power plant, for example, an overload condition may arise when the total current draw exceeds the rated capacity. With respect to a data communications pathway, an overload condition may arise when the total data transfer rate exceeds the pathway's actual capacity, thereby corrupting the data in transmission. In certain situations such as water supply or warehousing of materials, an overload condition may also indicate that although user demands are currently being met, reserve or buffer capacity is being depleted.
Depending on the nature of the resource, the consequences of an overload condition will vary, possibly including the need for an offline period for resource recovery (e.g., cooling of a power generation system or replenishment of a reservoir) or the need to expend present capacity in order to repeat a use that was attempted in the past but failed because of the overload (e.g., retransmission of a data packet corrupted by a collision). The resource may even become temporarily or permanently unable to regain its former capacity. In cases where the sum of the n usage rates ui may exceed the value R, it is desirable to control the usage rates in some fashion so as to avoid overload conditions.